package leetcode_21_40;

import java.util.ArrayList;
import java.util.List;

public class countAndSay_38 {
    /**
     *外观数列
     * 描述https://leetcode.cn/problems/count-and-say/
     * 思路是根据不同数字进行区分，划区，想法是递归
     * 实现很简单，但是太慢了
     * 12ms
     * @param n
     * @return
     */
    public static String countAndSay(int n) {
        List<Character>str=new ArrayList<>();
        str.add('1');
        return function(n,str);
    }
    static String function(int n,List<Character> lastStr){
        if(n==1) {
            String ans="";
            for (char c:lastStr )
                ans+=c;
            return ans;
        };
        List<Character>nowStr=new ArrayList<>();
        char lastChar=lastStr.get(0);
        int count=0;
        for(int i=0;i<lastStr.size();i++){
            //跳过第一个，判断当前字符是否与上一个字符相同
            if( i !=0 && lastStr.get(i)!=lastChar){       //不同则将之前的添加进去
                nowStr.add((char)(count+'0'));
                nowStr.add(lastChar);
                count=0;
            }
            count++;
            if(i==lastStr.size()-1){         //到最后一位时
                nowStr.add((char)(count+'0'));
                nowStr.add(lastStr.get(i));
            }
            lastChar = lastStr.get(i);
        }
        return function(n-1,nowStr);
    }

    /**
     * 官解
     * 也不咋地
     * 9ms
     * 遍历生成
     * @param n
     * @return
     */
    public String countAndSay2(int n) {
        String str = "1";
        for (int i = 2; i <= n; ++i) {
            StringBuilder sb = new StringBuilder();
            int start = 0;
            int pos = 0;

            while (pos < str.length()) {
                while (pos < str.length() && str.charAt(pos) == str.charAt(start)) {
                    pos++;
                }
                sb.append(Integer.toString(pos - start)).append(str.charAt(start));
                start = pos;
            }
            str = sb.toString();
        }

        return str;
    }

    /**
     *优化 递归
     * @param n
     * @return
     */
    public String countAndSay3(int n) {
        if(n == 1) return "1";
        String num = countAndSay3(n - 1);  //最深一层从1开始处理，回退处理num
        StringBuilder s = new StringBuilder();     //使用stringBuilder ，便于对字符串的处理
        for(int i=0; i<num.length(); i++) {
            int count = 1;
            while(i < num.length()-1 && num.charAt(i) == num.charAt(i+1)) {    //判断当前字符是否与上一个字符相同
                count++;
                i++;
            }
            s.append(count);
            s.append(num.charAt(i));
        }
        return s.toString();
    }
}
